﻿/*

 * Copyright (c) 2013 Diorge Brognara, Renan Peixoto

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

*/

using System;
using System.Collections.Generic;

namespace Grafos {
    /// <summary>
    /// Especialização de Grafo, representa uma árvore
    /// </summary>
    /// <remarks>
    /// Uma árvore é considerada um grafo sem presença ciclos
    /// Quando a propriedade ModoSeguro é falsa, essa classe difere da classe Grafo somente por não permitir loops
    /// Para conferir se a árvore realmente respeita as propriedades de árvore (sem ciclos, |E| = |V| - 1), utilize o método ÉÁrvore
    /// </remarks>
    /// <seealso cref="Grafo.ÉÁrvore"/>
    public class Árvore : Grafo {

        /// <summary>
        /// Quando verdadeiro, assegura que todas as arestas adicionadas não criam ciclos
        /// </summary>
        /// <remarks>
        /// Há uma perda de performance quando ativado, devido a verificação de ciclos a cada aresta adicionada
        /// É recomendado deixar como false durante a aplicação de algoritmos que incluem arestas intesivamente
        /// Caso o algoritmo deva ser testado, utilize o método ÉÁrvore após a execução
        /// Valor padrão é false
        /// </remarks>
        /// <example>
        /// <code>
        /// Árvore a = new Árvore();
        /// a.ModoSeguro = true;
        /// a.AdicionarVértice("v1");
        /// a.AdicionarVértice("v2");
        /// a.AdicionarAresta("v1", "v2");
        /// a.AdicionarAresta("v2", "v1"); // causa erro
        /// </code>
        /// </example>
        /// <seealso cref="Grafo.ÉÁrvore"/>
        public bool ModoSeguro { get; set; }

        /// <summary>
        /// Adiciona uma nova aresta à árvore
        /// </summary>
        /// <param name="a">Aresta a ser adicionada</param>
        /// <remarks>Quando ModoSeguro for ativado, faz verificação para evitar criação de ciclos</remarks>
        /// <exception cref="ArgumentException">É tentado adicionar um loop, ou um ciclo quando o Modo Seguro está ativo</exception>
        /// <seealso cref="ModoSeguro"/>
        public override void AdicionarAresta(Aresta a) {
            if (a.ÉLoop)
                throw new ArgumentException("Árvores não podem conter loops");

            base.AdicionarAresta(a);

            if (ModoSeguro && PossuiCiclo()) {
                Arestas.Remove(a);
                throw new ArgumentException("Tentativa de criar um ciclo na árvore");
            }
        }

        /// <summary>
        /// Adiciona uma nova aresta à árvore, dados dois vértices
        /// </summary>
        /// <param name="v1">Uma das extremidades da aresta</param>
        /// <param name="v2">Uma das extremidades da aresta</param>
        /// <exception cref="ArgumentException">É tentado adicionar um loop, ou um ciclo quando o Modo Seguro está ativo</exception>
        /// <seealso cref="ModoSeguro"/>
        public override void AdicionarAresta(Vértice v1, Vértice v2) {
            AdicionarAresta(new Aresta(v1, v2));
        }

        /// <summary>
        /// Adiciona uma nova aresta à árvore, dado o nome de dois vértices da árvore
        /// </summary>
        /// <param name="v1">Nome de uma das extremidades da aresta</param>
        /// <param name="v2">Nome de uma das extremidades da aresta</param>
        /// <exception cref="ArgumentException">É tentado adicionar um loop, ou um ciclo quando o Modo Seguro está ativo,
        /// ou o grafo não possui vértices com os nomes passados</exception>
        /// <seealso cref="ModoSeguro"/>
        public override void AdicionarAresta(string v1, string v2) {
            AdicionarAresta(BuscarVértice(v1), BuscarVértice(v2));
        }

        /// <summary>
        /// Adiciona uma coleção de arestas à árvore
        /// </summary>
        /// <param name="arestas">Pares de string que representam o nome de dois vértices que são a extremidade</param>
        /// <remarks>
        /// Cada par (ou tupla) de duas strings representa o nome de dois vértices que foram uma aresta
        /// Caso ocorra um erro na inserção de uma aresta, todas as arestas anteriores serão adicionadas, e as posteriores, abortadas
        /// </remarks>
        /// <example>
        /// <code>
        /// Árvore a = new Árvore();
        /// a.AdicionarVértice("A", "B", "C");
        /// a.AdicionarArestas(new Tuple&lt;string, string&gt;("A", "B"), new Tuple&lt;string, string&gt;("B", "C"));
        /// </code>
        /// </example>
        /// <exception cref="ArgumentException">É tentado adicionar um loop, ou um ciclo quando o Modo Seguro está ativo,
        /// ou o grafo não possui vértices com os nomes passados</exception>
        /// <seealso cref="ModoSeguro"/>
        public override void AdicionarAresta(params Tuple<string, string>[] arestas) {
            foreach (Tuple<string, string> a in arestas) {
                AdicionarAresta(a.Item1, a.Item2);
            }
        }

        /// <summary>
        /// Calcula o código de Prüfer da árvore
        /// </summary>
        /// <returns>Um código único para a topologia da árvore</returns>
        public string[] CódigoDePrüfer() {
            string[] código = new string[QuantidadeArestas - 1];
            FilaDePrioridadesVértice Q = new FilaDePrioridadesVértice();
            Q.Comparador = new ComparadorNome();
            Vértice u, pai = null;
            int atual = 0;
            Grafo g = this.Cópia();

            foreach (Vértice v in Vértices.Values) {
                Vértice vert = g.BuscarVértice(v.Nome);
                Q.Add(vert);
            }

            while (g.QuantidadeArestas > 1) {
                Q.Sort();
                u = Q[0];
                for (int i = 0; i < Q.Count; i++) {
                    if (Q[i].ÉFolha()) {
                        u = Q[i];
                        pai = u.Vizinhança()[0];
                        g.RemoverVértice(u.Nome);
                        Q.RemoveAt(i);
                        break;
                    }
                }

                código[atual] = pai.Nome;
                atual++;
            }

            return código;
        }


        /// <summary>
        /// Cria uma árvore a partir de uma lista de vértices
        /// </summary>
        /// <param name="vértices">Lista de vértices com Pi já calculado</param>
        /// <param name="modoSeguro">Indica se a árvore deve verificar presença de ciclos</param>
        /// <returns>Uma nova árvore que respeita os predecessores passados</returns>
        /// <remarks>
        /// Acionar o modo seguro pode causar problemas de performance, especialmente com muitos vértices
        /// A propriedade Pi dos vértices é utilizada para mapear os predecessores
        /// </remarks>
        /// <example>
        /// <code>
        /// Vértice[] v = Vértice.CriarConjuntoVértices("V", 4);
        /// v[0].Pi = null; // raíz
        /// v[1].Pi = v[0];
        /// v[2].Pi = v[0];
        /// v[3].Pi = v[2];
        /// Árvore a = Árvore.GerarDePredecessores(v, true);
        /// // forma a árvore de vértices "V1", "V2", "V3", "V4", com as arestas
        /// // V1-V2, V1-V3, V3-V4
        /// </code>
        /// </example>
        public static Árvore GerarDePredecessores(IEnumerable<Vértice> vértices, bool modoSeguro) {
            Árvore a = new Árvore();
            a.ModoSeguro = modoSeguro;
            Vértice novo;

            // cria o novo conjunto de vértices, copiando o antigo
            foreach (Vértice v in vértices) {
                novo = new Vértice(v.Nome);
                novo.Pi = v.Pi;
                novo.Lambda = v.Lambda;
                novo.Tag = v.Tag;
                a.AdicionarVértice(novo);
            }

            // atualiza o Pi de cada vértice para apontar para os novos vértices
            foreach (Vértice v in a.Vértices.Values) {
                if (v.Pi != null)
                    v.Pi = a.Vértices[v.Pi.Nome];
            }

            // cria as arestas a partir do Pi
            foreach (Vértice v in a.Vértices.Values) {
                if (v.Pi != null)
                    a.AdicionarAresta(v, v.Pi);
            }

            return a;
        }

    }
}
